package com.sfx.算法专题.双指针.n数之和;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-07-26
 * Time: 10:28
 */
public class Code_5_threeSum {
    static class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            for(int i = 0;i<nums.length;++i) {//固定一个数字
                if(i>=1 && nums[i] == nums[i-1]) continue;
                int l = i+1;
                int r = nums.length - 1;
                while(l < r) {
                    int sum = nums[i] + nums[l] + nums[r];
                    if(sum == 0) {
                        List<Integer> list = Arrays.asList(nums[i],nums[l],nums[r]);
                        res.add(list);
                        //注意去重
                        while(l<r &&nums[l] == nums[l+1]) l++;
                        while (l<r && nums[r] == nums[r-1]) r--;
                        l++;
                        r--;
                    } else if(sum > 0) {
                        r --;
                    }else {
                        l++;
                    }
                }
            }
            return res;
        }
    }
    public static void main(String[] args) {
        int[] nums = {-2,0,0,2,2};
        Solution solution = new Solution();
        solution.threeSum(nums);
    }
}